﻿ Restricted G-systems

## Restricted G-systems #### Restricted G-system

Let r be the number of instances in G-system. For some systems G(n,k) we can find such restriction r<n^k, that it holds:

```   u(i,j) = n^j * g(i) mod(r-1)
```

The system G(n,k,r) with such a property is called restricted G-system. It contains instances {0,1,...r-1}. E.g. the complete system G(3,3)=G(3,3,27) has r=3^3=27 instances. The restricted system G(3,3,14) has r=14 instances:

```          0
```
```          1   3   9
```
```          2   6  18            0
```
```          4  12  10            1  3  9
```
```          5  15  19            2  6  5
```
```          7  21  11            4 12 10
```
```          8  24  20            7  8 11
```
```         13                   13
```
```         14  16  22
```
```         17  25  23
```
```         26
```

Instances of restricted G-systems

#### Trivial system

Trivial system is such restricted system G(n,k,r), at which:

```   r mod k = 2
```

All complete systems G(n,p), p is prime, are trivial. In previous example: G(3,3,14) is trivial because 14 mod 3 = 2; G(3,3,27) is not trivial.

Duality

Two trivial systems G(n1,k,r), G(n2,k,r) are dual if

```   n1 *n2 = 1 mod (r-1)
```

#### Primitive roots

Let p=r-1 be prime.
Searching for trivial systems G(n,k,r) is equivalent to searching for primitive roots of prime p=r-1.
E.g. there exists p-1=12 trivial systems in case r=14:

• φ( 1) = 1 for k= 1
• φ( 2) = 1 for k= 2
• φ( 3) = 2 for k= 3
• φ( 4) = 2 for k= 4
• φ( 6) = 2 for k= 6
• φ(12) = 4 for k=12

It holds: φ(1)+φ(2)+φ(3)+φ(4)+φ(6)+φ(12) = 1+1+2+2+2+4 = p-1 = 12.

The degrees n of trivial systems with order k=r-2=p-1 are primitive roots of prime p.
E.g.: prime p=13 has four primitive roots: 2,7,6,11. This roots correspond to degrees n of dual systems:
G(2,12,14) <->G(7,12,14), G(6,12,14) <->G(11,12,13).

#### Wilson theorem

Let p=r-1 be prime. There exists:

• (r-2)/2 - 1 of dual systems; product of all their degrees n is 1 mod (r-1)
• one system n=1; n= 1 mod (r-1)
• one system n=r-2; n=-1 mod (r-1)

From it follows:

```   (r-2)! = -1 mod (r-1)
```

i.e. Wilson theorem.

#### N-classes in trivial systems

Assume trivial systems G(n,k,r) with r-1 = (n^k-1)/(n-1). For N-classes g(j) it holds:

```   (n^j-1)*g(j) mod (r-1) = b*n^(j-1); gcd(j, k) = 1.
```

E.g. G(3,3,14) has all its self-classes natural; r-1 = ( 3^3-1) (3-1) = 26/2 = 13

```Instances    Differences  Type Nb
```
```   0            -           -
```
```   1  3  9      2  6        N2
```
```   2  6  5      3  1        N1
```
```   4 12 10      6  2        N2
```
```   7  8 11      1  3        N1
```
```  13            -           -
```
```
```

On the contrary G(3,4,41) has only 2 natural classes; r-1 = ( 3^4-1) (3-1) = 80/2 = 40

```Instances       Differences  Type Nb
```
```   0             -             -
```
```   1  3  9 27    2  6 18       N2 (j=1)
```
```   2  6 18 14    4  8  4       -
```
```   4 12 36 28    8 16  8       -
```
```   5 15         10             -
```
```   7 21 23 29   14  2  6       -
```
```   8 24 32 16    8  8  8       -
```
```  10 30         20             -
```
```  11 33 19 17    6  2 14       -
```
```  13 39 37 31   18  6  2       N2 (j=3)
```
```  20             -             -
```
```  22 26 38 34    4  8  4       -
```
```  25 35         10             -
```
```  40             -             -
```
```b = 1:
```
``` j = 1:  (3^1-1)* g (mod 40)   =  1   -   no solution
```
``` j = 2:  (3^2-1)* g (mod 40)   =  3   -   no solution
```
``` j = 3:  (3^3-1)* g (mod 40)   =  9   -   no solution
```
```b = 2:
```
``` j = 1:  (3^1-1)* g (mod 40)   = 2*1  -   g =  1
```
``` j = 2:  (3^2-1)* g (mod 40)   = 2*3  -   no solution
```
``` j = 3:  (3^3-1)* g (mod 40)   = 2*9  -   g = 13
```

The last example shows N-classes for b = 1 in G(3,5,122); r-1 = ( 3^5-1) (3-1) = 242/2 = 121

```Instances               Type Nb
```
```    0                      -
```
```    1   3   9  27  81      -
```
```    2   6  18  54  41      -
```
```    4  12  36 108  82      -
```
``` *  5  15  45  14  42      N1  (j=3)
```
```    7  21  63  68  83      -
```
```    8  24  72  95  43      -
```
```   10  30  90  28  84      -
```
```   11  33  99  55  44      -
```
```   13  39 117 109  85      -
```
```   16  48  23  69  86      -
```
```   17  51  32  96  46      -
```
```   19  57  50  29  87      -
```
``` * 20  60  59  56  47      N1  (j=4)
```
```   22  66  77 110  88      -
```
```   25  75 104  70  89      -
```
```   26  78 113  97  49      -
```
```   31  93  37 111  91      -
```
```   34 102  64  71  92      -
```
```   35 105  73  98  52      -
```
```   38 114 100  58  53      -
```
```   40 120 118 112  94      -
```
``` * 61  62  65  74 101      N1  (j=1)
```
```   67  80 119 115 103      -
```
``` * 76 107  79 116 106      N1  (j=2)
```
```  121                      -
```
``` j = 1:  (31-1) gr (mod 121) =  1 -  g  =  61
```
``` j = 2:  (32-1) gr (mod 121) =  3 -  g  =  76
```
``` j = 3:  (33-1) gr (mod 121) =  9 -  g  =   5
```
``` j = 4:  (34-1) gr (mod 121) = 27 -  g  =  20
```

#### Excerpt from the Gauss work

Gauss works with restricted system R(26,6,32).

```n=26 <-> t=3; k=6; r=32;  3^5=26 mod 31;
```
```n^k-1= 308915775 = 31*9965025
```
```R(26,6,32):
```
``` 0
```
``` 1 26 25 30  5  6    (1)  
```
``` 2 21 19 29 10 12    (19) 
```
``` 3 16 13 28 15 18    (3)  
```
``` 4 11  7 27 20 24    (27) 
```
``` 8 22 14 23  9 17    (9)  
```
```31
```
```32-2=k(m-2)=6*5=3
```
```t^(m-2) = n (mod(r-1))
```
```--------------
```
```n=6
```
```n^k-1= 6^6-1= 46655 = 31*1505
```
```--------------
```
```R= 3, e= 5
```
```R^(b*e+a) mod 31:
```
``` a\b|  0   1   2   3   4   5
```
``` ---+------------------------
```
```  0 |  1  26  25  30   5   6
```
```  1 |  3  16  13  28  15  18
```
```  2 |  9  17   8  22  14  23
```
```  3 | 27  20  24   4  11   7
```
```  4 | 19  29  10  12   2  11
```

Schematic algebra